/*
 * @lc app=leetcode.cn id=105 lang=javascript
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  const mapInoder = new Map();
  // 缓存inorder 值->索引
  // 方便preorder中拿到根节点的值时，可以快速获取到左右节点的位置
  for (let i = 0; i < inorder.length; i++) {
    mapInoder.set(inorder[i], i);
  }
  // 构建根节点以及根节点的左右子树根
  const createRoot = (pLeft, pRight, iLeft, iRight) => {
    // 左索引超过右索引，到达边界。
    if (pLeft > pRight) return null;
    // 前序遍历第一个必然是根节点
    let rootVal = preorder[pLeft];
    // 构建根节点
    const root = new TreeNode(rootVal);
    // 从缓存中找到根节点的在中序中的位置，方便定位左右子树
    const inorderMidIndex = mapInoder.get(rootVal);
    // 左子树的节点数
    const leftNum = inorderMidIndex - iLeft;
    // 构建左右子树的根
    root.left = createRoot(pLeft + 1, pLeft + leftNum, iLeft, inorderMidIndex - 1);
    root.right = createRoot(pLeft + leftNum + 1, pRight, inorderMidIndex + 1, iRight);
    return root;
  };

  return createRoot(0, preorder.length - 1, 0, inorder.length);
};
// @lc code=end
